/*
 * Copyright 2003-2005 (c) Live Media Pty Ltd. <argot@einet.com.au> 
 *
 * This software is licensed under the Argot Public License 
 * which may be found in the file LICENSE distributed 
 * with this software.
 *
 * More information about this license can be found at
 * http://www.einet.com.au/License
 * 
 * The Developer of this software is Live Media Pty Ltd,
 * PO Box 4591, Melbourne 3001, Australia.  The license is subject 
 * to the law of Victoria, Australia, and subject to exclusive 
 * jurisdiction of the Victorian courts.
 */

#include "../TypePlatform.h"
#include "intmap.h"

/*
 * int hash(int key)
 * 
 * fast integer hash function taken from
 * http://www.concentric.net/~Ttwang/tech/inthash.htm
 */
int inthash(int key)
{
  key += (key << 12);
  key ^= (key >> 22);
  key += (key << 4);
  key ^= (key >> 9);
  key += (key << 10);
  key ^= (key >> 2);
  key += (key << 7);
  key ^= (key >> 12);
  return key;
}

/*
 * intmap_create( int powersize )
 * 
 * Creates a integer map.  The powersize value
 * sets the initial size of the base hashtable.
 * It 2^(powersize).  So a value of 2 will create
 * a hashtable of 4.  3 creates 8, 4 creates 16, etc.
 */
void intmap_init( intmap * im, int powersize )
{
  unsigned int i;
  
  if ( powersize <= 0 || powersize >= 16 )
  		powersize = 3;
 
  im->table_size = 2<<powersize;
  im->table_f = (intmap_item **)malloc(sizeof(intmap_item *)*(im->table_size));
  im->table_b = (intmap_item **)malloc(sizeof(intmap_item *)*(im->table_size));
  for (i=0; i<(im->table_size); ++i) im->table_f[i] = (intmap_item *)0;
  for (i=0; i<(im->table_size); ++i) im->table_b[i] = (intmap_item *)0;
  im->mask = im->table_size-1;  
  im->count = 0;
  im->current = (intmap_item *)0;
}

/*
 * intmap_destroy( intmap * im )
 * 
 */
void intmap_destroy( intmap * im )
{
	free( im->table_f );
	free( im->table_b );
	free( im );
}

void intmap_clear( intmap * im )
{
	free( im->table_f );
	free( im->table_b );	
}
/*
 * intmap_find( intmap * im, int key )
 * 
 * find an element.  return true if successful.
 */
intmap_rc intmap_find( intmap * im, int key )
{
  register intmap_item *item;
  register int hashvalue = inthash(key);

  for (item = im->table_f[ hashvalue & im->mask ]; item != 0; item = item->next_f)
  {
    if ((hashvalue == item->hash_f) && (key == item->key))
    {
      im->current = item;
      return INTMAP_OK;
    }
  }
  return INTMAP_ERROR;
}

/*
 * intmap_find( intmap * im, int key )
 * 
 * find a key from value.  return true if successful.
 */
intmap_rc intmap_find_key( intmap * im, int value )
{
  intmap_item *item;
  int hashvalue = inthash(value);

  for (item = im->table_b[ hashvalue & im->mask ]; item != 0; item = item->next_b)
  {
    if ((hashvalue == item->hash_b) && (value == item->value))
    {
      im->current = item;
      return INTMAP_OK;
    }
  }
  return INTMAP_ERROR;
}

/*
 * intmap_add( intmap * im, int key, int value )
 * 
 * Add an element to the intmap.
 */
intmap_rc intmap_add( intmap * im, int key, int value, void * data )
{
	register intmap_item * new_item, * item;
	register int hash = inthash(key);
	register int index = (hash & im->mask);
	
	/* return false if key already there. */
	for (item = im->table_f[ index ]; item != 0; item = item->next_f)
	{
	  if ((hash == item->hash_f) && (key == item->key))
	  {
	  	im->current = item;
	  	return INTMAP_ERROR;
	  }
	}
	
	new_item = (intmap_item *) malloc( sizeof( struct intmap_item ));
	new_item->key = key;
	new_item->value = value;
	new_item->data = data;
	
	new_item->hash_f = hash;
	new_item->next_f = im->table_f[ index ];
	im->table_f[index] = new_item;
	
	/* now calculate the backwards map. */
	hash = inthash(value);
	index = (hash & im->mask);
	
	new_item->hash_b = hash;	
	new_item->next_b = im->table_b[ index ];
	im->table_b[index] = new_item;

	/* set current and increment. */
	im->current = new_item;
	im->count++;
	return INTMAP_OK;
}

intmap_rc intmap_remove( intmap * im )
{
	register intmap_item **ip,*item;
	register int index;
	
	if ( im->current == 0 )
		return INTMAP_ERROR;
	
	item = im->current;
	
	/* remove forward reference. */
	index = im->current->hash_f & im->mask;	
	for (ip = &im->table_f[index]; *ip != item; ip = &(*ip)->next_f)
    	;
  	*ip = (*ip)->next_f;
  	
  	/* remove backward reference */
  	index = im->current->hash_b & im->mask;
	for (ip = &im->table_b[index]; *ip != item; ip = &(*ip)->next_b)
    	;
  	*ip = (*ip)->next_b;
  
  	/* decrement and free item. */
  	im->count--;
  	free( item );
  	
  	/* set current to empty. */
  	im->current = 0;
  	
  	return INTMAP_OK;
}

void intmap_iterator_init( intmap_iterator * imi, intmap * im )
{
	imi->map = im;
	imi->index = -1;
	imi->current = NULL;
}

int intmap_iterator_key( intmap_iterator * imi )
{
	return imi->current->key;
}

bool intmap_iterator_next( intmap_iterator * imi )
{
	if ( imi->index >= (int) imi->map->table_size )
		return false;

	if ( imi->current != NULL )
	{
		imi->current = imi->current->next_f;
		if ( imi->current != NULL )
			return true;	
	}

	while ( imi->current == NULL && imi->index < (int) imi->map->table_size )
	{
		imi->index++;
		imi->current = imi->map->table_f[ imi->index ];
	}
	
	if ( imi->current == NULL )
		return false;
		
	return true;
}
